package com.demo.java.OD351_400.OD373;

import java.util.Scanner;
import java.util.Stack;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【二叉树遍历(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146232447
 */
public class OdMain {
    static class TreeNode {
        char data;  // 当前节点的值
        TreeNode leftChild;  // 左子节点
        TreeNode rightChild;  // 右子节点

        // 构造函数
        TreeNode(char data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }
    }

    // 构建二叉树
    public static TreeNode createTreeNode(String str) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = null;
        TreeNode currentNode = null;
        boolean isLeftChild = false;  // 用于标记是添加左子节点还是右子节点

        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            switch (ch) {
                case '{':
                    stack.push(currentNode);  // 将当前节点入栈，标记当前进入新的子树
                    isLeftChild = true;  // 进入左子树
                    break;
                case ',':
                    isLeftChild = false;  // 逗号表示右子树
                    break;
                case '}':
                    stack.pop();  // 出栈，返回父节点
                    break;
                default:
                    currentNode = new TreeNode(ch);  // 创建一个新的节点
                    if (root == null) {
                        root = currentNode;  // 如果是根节点
                    } else {
                        if (isLeftChild) {
                            stack.peek().leftChild = currentNode;  // 将当前节点作为父节点的左子节点
                        } else {
                            stack.peek().rightChild = currentNode;  // 将当前节点作为父节点的右子节点
                        }
                    }
                    break;
            }
        }
        return root;
    }

    // 中序遍历
    public static void inOrderTraversal(TreeNode root) {
        if (root == null) {
            return;  // 递归终止条件
        }

        inOrderTraversal(root.leftChild);  // 遍历左子树
        System.out.print(root.data);  // 输出当前节点的数据
        inOrderTraversal(root.rightChild);  // 遍历右子树
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.nextLine();  // 读取输入的二叉树结构字符串
        TreeNode root = createTreeNode(inputStr);  // 构建二叉树
        inOrderTraversal(root);  // 进行中序遍历
        System.out.println();  // 输出换行符
    }
}